Home | | Latest | About | Random
# Solution space to linear recurrences.
Given an $k$-th order linear homogeneous linear recurrence $$
a_{n+k}+c_{1}a_{n+k-1}+\cdots+c_{k}a_{n}=0
$$we seek all sequences $(a_{n})$ over field $\mathbb{C}$, say that solves it. We claim the space is $k$-dimensional.
Denote the space of sequences $\mathbb{C}^\mathbb{N}$ with usual entry-wise addition and scaling. And let $T:\mathbb{C}^\mathbb{N}\to \mathbb{C}^\mathbb{N}$ to be the left-shift operator, $T(a_{n})=a_{n+1}$. Then the linear recurrence can be re-expressed as $$
(T^k + c_{1}T^{k-1} +\cdots+c_{k}I)a_{n}=0
$$
Namely the set of all sequences solving this homogeneous linear recurrence is the kernel of the operator $p(T)$ for some polynomial $p$.
===
We shall show some generic lemmas.
>**Lemma 1.** If $T,U:V\to V$ are two linear operators where $U$ is onto and both $\ker(T)$ and $\ker(U)$ are finite dimensional. Then $ker(TU)$ is finite dimensional, in particular $\dim(\ker TU)=\dim(\ker T)+\dim(\ker U)$.
**Proof.** Since both $T,U$ have finite dimensional kernels, say we have $x_{1},\ldots,x_{n}$ be a basis to $\ker T$ and $y_{1},\ldots,y_{m}$ be a basis to $\ker U$. Since $U$ is onto, we can find pre-images $z_{i}$ such that $U(z_i)=x_i$. We claim the set $$
\beta = \{z_{1},\ldots,z_{n},y_{1},\ldots,y_m\}
$$ form a basis to $\ker TU$. Note by construction, it is clear that $z_{i},y_{j}$ are mapped to zero by $TU$.
We show the set $\beta$ is linearly independent. Suppose some linear combination $a_{1}z_{1}+\cdots+a_{n}z_{n}+b_{1}y_{1}+\cdots+b_{m}y_{m}=0$, then by applying $U$, we get $a_{1}x_{1}+\cdots+a_{n}x_{n}=0$. And since the $x_{i}$'s form a basis, whence linearly independent, we have $a_{i}=0$ for each $i$. Then this leaves $b_{1}y_{1}+\cdots+b_{m}y_{m}=0$. And as $y_{i}$'s' form a basis, they are linearly independent, so the $b_{i}$ are also all zero. Thus the set $\beta$ is linearly independent.
Now take some element $x\in\ker TU$. Namely $TUx=0$. Note $Ux$ is in $\ker T$, which we can write $Ux = c_{1}x_{1}+\cdots + c_{n}x_{n}$. So as $U(c_{1}z_{1}+\cdots+c_{n}z_{n}-x) = 0$, we have that $x=c_{1}z_{1}+\cdots+c_{n}z_{n}+y$ for some $y\in \ker U$. Whence $x=c_{1}z_{1}+\cdots+c_{n}z_{n}+d_{1}y_{1}+\cdots d_{m}y_{m}$. Namely, $x\in \mathrm{span}(\beta)$.
Thus $\beta$ forms a basis for $\ker TU$, and that $\ker TU$ has dimension $n+m=\dim\ker T + \dim \ker U$. $\blacksquare$
===
We can now immediately apply this. If we fix any complex number $\lambda \in \mathbb{C}$, we claim the operator $T-\lambda I$ on the sequence space $\mathbb{C}^\mathbb{N}$ is onto with kernel of dimension 1, where $T$ is the left-shift operator.
Indeed, by the fundamental theorem of algebra, any monic polynomial $p(T)$ splits as $(T-\lambda_{1}I)\cdots (T-\lambda_{k}I)$, where $\lambda_{i}$ not necessarily distinct. Noting that composition of onto operators remain onto, inductively we see that $\ker p(T)$ is of dimension $k$.
===
This is also true for a $k$-th order linear DE, the operator $D:\mathbb{C}^{\infty}\to \mathbb{C}^\infty$ where $D=\frac{d}{dz}$ is such that $D-\lambda I$ is also onto for any $\lambda\in\mathbb{C}$. Hence the $k$-th order linear DE has a $k$-dimensional solution space as well!
===
To construct the basis for the space of sequences that lie in the kernel of $p(T)$ for some monic $p$, we construct a basis for $\ker (T-\lambda I)^{a}$ and claim that if $p,q$ are coprime, then $\ker(p(T)q(T)) = \ker p(T)\oplus \ker q(T)$.
One can verify that indeed $\ker(T-\lambda I)$ is one-dimensional and spanned by $(x_{n})=(1,\lambda,\lambda^{2},\ldots)$.
What about $\ker(T-\lambda I)^{2}$? By what is suggested in the lemma above, we seek the pre-image of $(1,\lambda,\lambda^{2},\ldots)$ under $T-\lambda I$. This means we need $y_{n+1}-\lambda y_{n}=\lambda^{n}$. Taking $y_{0}=0$, we have $y_{1}=1$, $y_{2}=2\lambda$, $y_{3}=3\lambda^{2}$, etc. So we see that $y_{n}=n\lambda^{n-1}$ works. Indeed, $(n+1)\lambda^{n}-\lambda n \lambda^{n-1}=\lambda^{n}$. So $(\lambda^{n})$ and $(n\lambda^{n-1})$ span $\ker (T-\lambda I)^{2}$.
To get a basis for $\ker(T-\lambda I)^{3}$, find the pre-image of $(1,\lambda,\lambda^{2},\ldots)$ under $(T-\lambda I)^{2}$. Note that $(T-\lambda I)^{2}(n(n-1)\lambda^{n-2})$ gives $(T-\lambda I)((n+1)n\lambda^{n-1} - n(n-1)\lambda^{n-1})=(T-\lambda I)(2n\lambda^{n-1})=2\lambda^{n}$.
So $(\frac{1}{2}n(n-1)\lambda^{n-2})$, along with $(n\lambda^{n-1})$ and $(\lambda^{n})$ form a basis to $\ker(T-\lambda I)^{3}$. If $\lambda$ is not zero, we can rescale and recombine them to get $(n^{2}\lambda^{n}), (n\lambda^{n}),(\lambda^{n})$. One can generalize this to the $k$-th power case.
When $\lambda=0$, then we have $\ker(T^{k})=\mathrm{span}(e_{1},e_{2},\ldots,e_{k})$, where $e_{i}$ is the sequence where the $i$-th entry is $1$ and rest $0$.
This gives a complete basis set to $\ker(p(T))$: Factorize $p$ into powers of irreducible linear terms $(T-\lambda I)^a$, and write out its basis as above.